package packbag;

/**
 * @Author Fizz Pu
 * @Date 2020/10/27 下午11:29
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

/**
 * 现有n种物品和一个背包
 * 物品i的重量是Wi, 价值是Vi, 背包容量是c
 * 如何选择物品，才能使得背包中的物品价值之和最大
 */

import java.util.Arrays;

/** 1. 方法一
 *模型： sum(Vi*Xi) , Sum(Wi*Xi)  <= c
 * 递归求解,对于物品序列 Item1, Item2, Item3,……, Itemi，考察Itemi是否放入背包
 * 假设此时背包容量为j, 背包的最优价值为m(i,j)
 * j < Wi Itemi根本放不进去,最优值是m(i-1, j)
 * j >= Wi 存在两种情况 Itemi放进去和Itemi不放进去，Itemi不放进去，最优值是m(i-1,j), Itemi放进去，最优值是m(i-1, j-Wi) + Vi,
 * 最后取最大值即可 ,最优值是Math.max(m(i-1, j), m(i-1, j - Wi) + Vi)
 *
 * 相当于填写二维矩阵，矩阵的行表示第i个物品,
 */


public class packbag0_1 {
    public static void main(String[] args) {

        // bagSize 背包容量
        // itemCount 物品个数
        int bagSize = 10, itemCount = 5;
        int[] weight = new int[] {2,2,6,5,4};
        int[] value = new int[] {6,3,5,4,6};

        // 背包容量从0开始
        int[][] dp = new int[itemCount][bagSize+1];

        // 初始化值,只有一个物品时
        for(int i = 0; i <= bagSize; ++i){
            int itemValue = value[0], itemWeight = weight[0];
            dp[0][i] = (i < itemWeight ? 0 : itemValue);
        }

        // 利用状态转移方程填表
        for(int itemIndex = 2; itemIndex <= itemCount; ++itemIndex){
            for(int bagWeight = 1; bagWeight <= bagSize; ++bagWeight){
                int weightI = weight[itemIndex-1], valueI = value[itemIndex-1];
                dp[itemIndex-1][bagWeight] = (bagWeight < weightI ? dp[itemIndex-2][bagWeight] :
                        Math.max(dp[itemIndex-2][bagWeight], dp[itemIndex-2][bagWeight-weightI] + valueI));
            }
        }

        // 打印最优值
        System.out.println(Arrays.deepToString(dp));
    }
}
